﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 判断线段相交
{
    class Program
    {
        static void Main(string[] args)
        {
            Point p1 = new Point(0, 0);
            Point p2 = new Point(4, 4);
            Point p3 = new Point(0, 4);
            Point p4 = new Point(4, 0);
            Line line1 = new Line(p1, p2);
            Line line2 = new Line(p3, p4);
            Program a = new Program();
            if (a.IsInterSect(line1, line2))
                Console.WriteLine("相交");
            else
                Console.WriteLine("不想交");
        }
        /// <summary>
        /// 判断两线段是否相交
        /// </summary>
        /// <param name="pline1"></param>
        /// <param name="pLine2"></param>
        /// <returns></returns>
        public Boolean IsInterSect(Line pLine1, Line pLine2)
        {
            //快速排斥
            if (IsInterSect(pLine1.Envelope, pLine2.Envelope))
            {
                //跨立实验
                if (CheckCross(pLine1, pLine2) && CheckCross(pLine2, pLine1))
                    return true;
                else
                    return false;
            }
            else
                return false;
        }
        /// <summary>
        /// 判断pLine2 跨立 pLine1
        /// </summary>
        /// <param name="pline1"></param>
        /// <param name="pLine2"></param>
        /// <returns></returns>
        public Boolean CheckCross(Line pLine1, Line pLine2)
        {
            Point P1 = pLine2.FromPoint;
            Point P2 = pLine2.ToPoint;
            Point Q1 = pLine1.FromPoint;
            Point Q2 = pLine1.ToPoint;
            //P1P2跨立Q1Q2
            //(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0 *为矢量叉积
            double V1 = VectorCrossProduct(P1.X - Q1.X, Q2.X - Q1.X, P1.Y - Q1.Y, Q2.Y - Q1.Y);
            double V2 = VectorCrossProduct(Q2.X - Q1.X, P2.X - Q1.X, Q2.Y - Q1.Y, P2.Y - Q1.Y);
            if (V1 * V2 >= 0)
                return true;
            else
                return false;
        }
        /// <summary>
        /// 矢量叉积
        /// </summary>
        /// <param name="x1"></param>
        /// <param name="x2"></param>
        /// <param name="y1"></param>
        /// <param name="y2"></param>
        /// <returns></returns>
        private double VectorCrossProduct(double x1, double x2, double y1, double y2)
        {
            return x1 * y2 - x2 * y1;
        }
        /// <summary>
        /// 判断两矩形是否相交
        /// </summary>
        /// <param name="Env1"></param>
        /// <param name="Env2"></param>
        /// <returns></returns>
        private Boolean IsInterSect(Envelope Env1, Envelope Env2)
        {
            double maxLeft = Env1.XMin >= Env2.XMin ? Env1.XMin : Env2.XMin;
            double minRight = Env1.XMax <= Env2.XMax ? Env1.XMax : Env2.XMax;
            double maxBottom = Env1.YMin >= Env2.YMin ? Env1.YMin : Env2.YMin;
            double minTop = Env1.YMax <= Env2.YMax ? Env1.YMax : Env2.YMax;
            if (maxLeft > minRight || maxBottom > minTop)
                return false;
            return true;
        }
    }
}
